package datastrucure.tree;

/**
 * @Author Fizz Pu
 * @Date 2021/4/19 下午3:32
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.util.*;


/**
 * tmp = [] result = [[],[]]
 * dfs(root, targetSum, sum):
 *   if(root == null):
 *          return;
 *
 *   sum += root.val;
 *   tmp.add(root.val)
 *
 *   if(root.left == null && root.right == null):
 *          handle result;
 *
 *  dfs(root.left);
 *  dfs(root.right);
 *  tmp删除最后一个元素
 *  sum -= root.val;
 */

public class Offer113 {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> tmp = new ArrayList<>();
    private int sum = 0;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }

    private void dfs(TreeNode root, int targetSum){
        if(root == null){
            return;
        }

        sum += root.val;
        tmp.add(root.val);

        if(root.right == null && root.left == null && this.sum == targetSum){
            res.add(new ArrayList<>(tmp));
        }

        dfs(root.left, targetSum);
        dfs(root.right, targetSum);

        tmp.remove(tmp.size() - 1);
        this.sum -= root.val; // 这个其实是没有作用的, 回到上一层后, 直接就减去了
    }
}
